|
In mathematics and theoretical computer science, a set constraint is an equation or an inequation between sets of terms. Similar to systems of (in)equations between numbers, methods are studied for solving systems of set constraints. Different approaches admit different operators (like "∪", "∩", "\", and function application)〔If ''f'' is an ''n''-ary function symbol admitted in a term, then "''f''(''E''1,...,''E''''n'')" is a set expression denoting the set , where ''E''1,...,''E''''n'' are set expressions in turn.〕 on sets and different (in)equation relations (like "=", "⊆", and "⊈") between set expressions. Systems of set constraints are useful to describe (in particular infinite) sets of ground terms.〔This is similar to describing e.g. a rational number as a solution to an equation ''a''⋅''x'' + ''b'' = 0, with integer coefficients ''a'', ''b''.〕 They arise in program analysis, abstract interpretation, and type inference. ==Relation to regular tree grammars== Each regular tree grammar can be systematically transformed into a system of set inclusions such that its minimal solution corresponds to the tree language of the grammar. For example, the grammar (terminal and nonterminal symbols indicated by lower and upper case initials, respectively) with the rules : is transformed to the set inclusion system (constants and variables indicated by lower and upper case initials, respectively): : This system has a minimal solution, viz. ("''L''(''N'')" denoting the tree language corresponding to the nonterminal ''N'' in the above tree grammar): : |- | ''BList1''S || = ''L''(''BList1''G) || = |} The maximal solution of the system is trivial; it assigns the set of all terms to every variable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Set constraint」の詳細全文を読む スポンサード リンク
|